package 队列;
/*
用队列实现栈:
    仅使用两个队列实现一个后入先出的栈,并支持普通栈的全部四种操作
        1.将元素x压入栈顶
        2.移除并返回栈顶元素
        3/返回栈顶元素
        4.如果栈是空的.返回true;否则,返回false
    当两个队列都为空,放到第一个队列;再次入栈时,放到不为空的队列;出栈时,出不为空的队列,出(size-1)个元素,剩下的就是要出栈的元素
 */

import java.util.LinkedList;
import java.util.Queue;

public class MyStack {
    //因为栈和队列的共同点是都可以用单项链表来实现,所以定义队列时,就使用链表

    public Queue<Integer> queue1;
    public Queue<Integer> queue2;
    public MyStack() {
        //定义队列
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        //入栈
        if(empty()){
            //同时都为空,就存入队列1
            queue1.offer(x);
        }
        //第二次之后入栈,就将数据放到不为空的队列
        if(!queue1.isEmpty()){
            queue1.offer(x);
        }else {
            queue2.offer(x);
        }
    }

    public int pop() {
        //按照栈的出栈顺序,出队列中存在的数据
        if(empty()){
            return -1;
        }
        if(!queue1.isEmpty()){
            //判断数据在队列1中
            int size = queue1.size();
            for (int i = 0; i < size-1; i++) {
                //将队列1的数据按照顺序存入队列2中,但是要保留队列中最后一个元素,最后一个元素对应的是栈的第一个出栈元素
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }else{
            //判断数据在队列2中
            int size = queue2.size();
            for (int i = 0; i < size-1; i++) {
                //将队列2的数据按照顺序存入队列1中,但是要保留队列中最后一个元素,最后一个元素对应的是栈的第一个出栈元素
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }

    public int top() {
        //返回栈顶,但是不出栈(队列)
        if(empty()){
            return -1;
        }
        if(!queue1.isEmpty()){
            //判断数据在队列1中
            int tmp = -1;//用一个标签
            int size = queue1.size();
            for (int i = 0; i < size; i++) {
                tmp = queue1.poll();
                queue2.offer(tmp);
            }
            return tmp;
        }else{
            //判断数据在队列2中
            int tmp = -1;//用一个标签
            int size = queue2.size();
            for (int i = 0; i < size; i++) {
                tmp = queue2.poll();
                queue1.offer(tmp);
            }
            return tmp;
        }
    }


    public boolean empty() {
        //判断两个链表是否都为空
        return queue1.isEmpty()&&queue2.isEmpty();
    }
}
